# -*- mode: snippet -*-
# name: geteuler
# key: geteuler
# --
ll get_euler(ll n) {
  ll res = n;
  for (ll i = 2; i <= n / i; ++i) {
    if (n % i == 0) {
      res = res / i * (i - 1);
      while (n % i == 0) {
	n /= i;
      }
    }
  }
  if (n > 1) res = res / n * (n - 1);
  return res;
}

